Exqule Forever

Nothing with me, but Forever.

CF1324F Maximum White Subtree

发布于 2020-10-02 | 分类于树、换根dp 、 CodeForces 、树形dp 、动态规划 | 3分钟 | 565字数

CF1324F Maximum White Subtree

题意

给定一棵 $n$ 个结点的树，每个点的颜色是黑白中的一种。对于每个结点 $u$ ，选出一棵包含点 $u$ 的连通子树，求其中白点数减去黑点数的最大值。

阅读全文 »

P1291 [SHOI2002]百事世界杯之旅

发布于 2020-10-02 | 分类于概率、期望、各省省选 | 3分钟 | 433字数

P1291 [SHOI2002]百事世界杯之旅

Meaning

考虑共有 $n$ 种卡片的抽卡游戏，每次等概率抽取一种卡片。求抽取到所有种类卡片的期望次数。

阅读全文 »

P1131 [ZJOI2007]时态同步

发布于 2020-10-02 | 分类于树、各省省选、树形dp 、动态规划 | 3分钟 | 415字数

P1131 [ZJOI2007]时态同步

Meaning

考虑边带权的树，我们每次操作可以使得一条边的权值加 1，求将每个叶子结点的深度相同最少需要的操作次数。

阅读全文 »

P4198 楼房重建

发布于 2020-10-01 | 分类于二分查找、线段树 | 5分钟 | 957字数

P4198 楼房重建

题意

考虑在一个二维平面上，x 轴表示在一条直线上大楼排列的坐标，y 轴表示大楼的高度，那么第 $i$ 栋大楼可以用 $(i,h_i)$ 表示。如果第 $i$ 栋大楼与第 $j$ 栋大楼满足 $i<j$ 且 $\frac{h_i}{i}\geq\frac{h_j}{j}$ ，那么第 $j$ 栋大楼被第 $i$ 栋大楼挡住而不可视见。求从 $(0,0)$ 最多能看到的大楼数量。

阅读全文 »

国庆集训 Test 1

发布于 2020-10-01 | 分类于概率、树、链表、贪心、树形dp 、动态规划 | 8分钟 | 1452字数

国庆集训 Test 1

阅读全文 »

HISTOGRA - Largest Rectangle in a Histogram

发布于 2020-09-30 | 分类于悬线法、单调栈、 SPOJ | 3分钟 | 397字数

HISTOGRA - Largest Rectangle in a Histogram

悬线法裸题。

题意

从 $1$ 到 $n$ 每个位置有一个高度为 $h_i$ ，宽度为 $1$ 的矩形。

求所有矩形覆盖面积中最大子矩形。

阅读全文 »

P2801 教主的魔法

发布于 2020-09-29 | 分类于分块、排序 | 4分钟 | 610字数

P2801 教主的魔法

分块裸题，作为初学者用来练手。

题意

维护长度为 $n$ 序列，有两种操作：

区间加法。
求区间中大于 $k$ 的数的个数。

阅读全文 »

USACO03FALL-Cow Exhibition G

发布于 2020-09-29 | 分类于背包dp 、 USACO | 2分钟 | 332字数

[USACO03FALL]Cow Exhibition G

题意

给定 $n$ 个数分别有 $2$ 个权值 $a_i,b_i$ ，选取一些数使得 $\sum a_i\geq 0,\sum b_i\geq 0$ 的条件下求 $\sum a_i+b_i$ 的最大值。

阅读全文 »

P1064 金明的预算方案

发布于 2020-09-29 | 分类于背包dp | 3分钟 | 462字数

P1064 金明的预算方案

存在依赖关系背包转化分组背包。

题意

给定 $n$ 个物品的价值和体积，他们之间存在简单的依赖关系，即一个结点要么是父亲结点，要么是儿子结点，且一个父亲结点最多有两个儿子结点。

阅读全文 »

USACO12OPEN-Bookshelf G

发布于 2020-09-29 | 分类于单调队列、 USACO 、动态规划-优化、线段树、动态规划 | 8分钟 | 1362字数

[USACO12OPEN]Bookshelf G

题意

考虑现在有 $n$ 本书并给定一个最大长度 $L$ ，第 $i$ 本书有高度 $h_i,w_i$ 。每次选取一段范围满足该段范围内的所有书的 $\sum w_i\leq L$ ，那么这次选取的贡献为 $\max\{h_i\}$ 。

阅读全文 »

1
2
3
4
…
7